關於 Search

如同第七天開頭提到，Sort 的功用在於幫助 Search 可以更快速。任何資料結構都是用來儲存資料，而如何取用是每一種資料結構的課題。目前介紹的資料結構是 Array 以及 Linked List，兩者的特性都是線性數列，在 Search 上的討論可以放在一起。

Linear Search

目前主流程式語言都有的基本語法 for-loop，包含 for、while 以及衍生的 for 語法糖家族（for...in、for...of），其核心精神是一個一個執行、檢查數列內的每個元素。

這邊叉題講一下封裝的好的 Array 函式，菜雞時期喜歡使用許許多多的 Array 函式來處理資料，例如：

const response = await axios.get('...');
const data = response.data;

data.forEach((item, index) => { ... });
const allowedData = data.filter((item, index) => { ... });
const hasCompleted = data.includes('foo');

forEach、filter、includes 等都會執行 For Loop，所以這邊執行了三個 for-loop，如果可以用一個 for 來執行呢？效能應該能有效提升。

如果用時間複雜度來看待：

# 一個 for loop
O(n)
# 三個 for loop
O(n) + O(n) O(n) = O(3n)
# --> 消除常數
O(n)

可以看出在 n 極大的情況下，兩者差距其實是沒有的。但實務上則是盡可能避免。

Binary Search

一個一個搜尋太慢了，所以聰明人想到，如果在 排列後 的數列內，可以藉由每一次找尋中間數來縮小搜尋範圍，最後逼近答案。

因為每次都找尋中間數，使得時間複雜度從 Linear Search 的 O(n) 縮減為 O(log n)。

一想到時間能縮減就感到很開心，但是前提千萬不能忘記：

• 排列後 的數列
• 排列後 的數列
• 排列後 的數列

如果數列沒有排列，只能乖乖用 Linear Search。

原理

# 排列後的數列，長度為 17，最小值為 2，最大值為 99。
2 5 8 13 16 19 20 23 40 45 66 67 71 74 87 98 99
# 找尋目標為 74

# 第一回合
# 長度 17，中間是第 9 個數 -> 40
# 40 小於 74，所以修改 最小值為 40 右邊的數 -> 45
# 範圍縮小為
2 5 8 13 16 19 20 23 40         45 66 67 71 74 87 98 99

# 第二回合
# 長度89，中間是第 4 個數 -> 71
# 71 小於 74，所以修改 最小值為 71 右邊的數 -> 74 ，此時不知道邊界是目標，只能繼續搜尋
# 範圍縮小為
2 5 8 13 16 19 20 23 40 45 66 67 71         74 87 98 99

# 第三回合
# 長度 4，中間是第 2 個數 -> 87
# 87 大於 74，所以修改 最大值為 40 左邊的數 -> 74 ，此時不知道邊界是目標，只能繼續搜尋
# 範圍縮小為
2 5 8 13 16 19 20 23 40 45 66 67 71         74         87 98 99

# 第四回合
# 因為最小值與最大值都在同一個數，比較該數是不是目標
# Bingo! 找到！
# 接著了解是第 14 個數， index 為 13
# 結束

用 Array 實作

來源

JS

/**
 * @param {number[]} arr
 * @param {number} low
 * @param {number} high
 * @param {number} targetVal
 */
const binarySearchWithRecursive = (arr, low, high, targetVal) => {
  if (high >= low) {
    const middle = (low + high) >> 1;

    if (arr[middle] === targetVal) {
      return middle;
    }

    if (arr[middle] > targetVal) {
      return binarySearchWithRecursive(arr, low, middle - 1, targetVal);
    } else {
      return binarySearchWithRecursive(arr, middle + 1, high, targetVal);
    }
  }

  return -1;
};

/**
 * @param {number[]} arr
 * @param {number} low
 * @param {number} high
 * @param {number} targetVal
 */
const binarySearchWithIterative = (arr, low, high, targetVal) => {
  while (low <= high) {
    const middle = (low + high) >> 1;

    if (arr[middle] == targetVal) {
      return middle;
    }

    if (arr[middle] < targetVal) {
      low = middle + 1;
    } else {
      high = middle - 1;
    }
  }

  return -1;
};

let arr = [2, 3, 4, 10, 40];
const n = arr.length;
const x = 10;
// const result = binarySearchWithRecursive(arr, 0, n - 1, x);
const result = binarySearchWithIterative(arr, 0, n - 1, x);

if (result === -1) {
  console.log("Element is not present in array");
} else {
  console.log("Element is present at index: " + result);
}

Java

public class BinarySearch {
    int binarySearchWithRecursive(int arr[], int low, int high, int targetVal) {
        if (high >= 1) {
            int middle = (low + high) >> 1;

            if (arr[middle] == targetVal) {
                return middle;
            }

            if (arr[middle] > targetVal) {
                return binarySearchWithRecursive(arr, low, middle - 1, targetVal);
            } else {
                return binarySearchWithRecursive(arr, middle + 1, high, targetVal);
            }
        }

        return -1;
    }

    int binarySearchWithIterative(int arr[], int low, int high, int targetVal) {
        while (low <= high) {
            int middle = (low + high) >> 1;

            if (arr[middle] == targetVal) {
                return middle;
            }

            if (arr[middle] < targetVal) {
                low = middle + 1;
            } else {
                high = middle - 1;
            }
        }

        return -1;
    }

    public static void main(String[] args) {
        BinarySearch ob = new BinarySearch();
        int arr[] = { 2, 3, 4, 10, 40 };
        int n = arr.length;
        int x = 10;
        // int result = ob.binarySearchWithRecursive(arr, 0, n - 1, x);
        int result = ob.binarySearchWithIterative(arr, 0, n - 1, x);

        if (result == -1) {
            System.out.println("Element not present");
        } else {
            System.out.println("Element found at index: " + result);
        }
    }
}

C

#include <stdio.h>

int binarySearchWithRecursive(int arr[], int low, int high, int target_val)
{
    if (high >= low)
    {
        int middle = (low + high) >> 1;

        if (arr[middle] == target_val)
        {
            return middle;
        }

        if (arr[middle] > target_val)
        {
            return binarySearchWithRecursive(arr, low, middle - 1, target_val);
        }
        else
        {
            return binarySearchWithRecursive(arr, middle + 1, high, target_val);
        }
    }

    return -1;
}

int binarySearchWithIterative(int arr[], int low, int high, int target_val)
{
    while (low <= high)
    {
        int middle = (low + high) >> 1;

        if (arr[middle] == target_val)
        {
            return middle;
        }

        if (arr[middle] < target_val)
        {
            low = middle + 1;
        }
        else
        {
            high = middle - 1;
        }
    }

    return -1;
}

int main()
{
    int arr[] = {2, 3, 4, 10, 40};
    int n = sizeof(arr) / sizeof(arr[0]);
    int x = 10;
    // int result = binarySearchWithRecursive(arr, 0, n - 1, x);
    int result = binarySearchWithIterative(arr, 0, n - 1, x);

    if (result == -1)
    {
        printf("Element is not present in array");
    }
    else
    {
        printf("Element is present at index %d\n", result);
    }

    return 0;
}

用 Linked List 實作

來源

JS

class node {
  /**
   * @param {number} val
   * @param {node} next
   */
  constructor(val) {
    this.val = val;
    this.next = null;
  }
}

/**
 * @param {node} node
 */
const printList = (node) => {
  let message = '';

  while (node !== null) {
    message += (node.val + ' ');
    node = node.next;
  }

  console.log(message);
};

/**
 * @param {node} headRef
 * @param {number} newVal
 */
const push = (headRef, newVal) => {
  let newNode = new node(newVal);
  newNode.next = headRef;
  headRef = newNode;
  return headRef;
};

/**
 * @param {node} start
 * @param {node} last
 */
const middleNode = (start, last) => {
  if (start === null) {
    return null;
  }

  let slow = start;
  let fast = start.next;

  while (fast !== last) {
    fast = fast.next;

    if (fast !== last) {
      slow = slow.next;
      fast = fast.next;
    }
  }

  return slow;
};

/**
 * @param {node} head
 * @param {number} targetVal
 */
const binarySearchLinkedList = (head, targetVal) => {
  let start = head;
  let last = null;

  do {
    let mid = middleNode(start, last);

    if (mid === null) {
      return null;
    }

    if (mid.val === targetVal) {
      return mid;
    } else if (mid.val < targetVal) {
      start = mid.next;
    } else {
      last = mid;
    }
  } while (last === null || last !== start);

  return null;
};

let head = null;

head = push(head, 2);
head = push(head, 3);
head = push(head, 5);
head = push(head, 10);
head = push(head, 15);
head = push(head, 20);

const x = 10;

if (binarySearchLinkedList(head, x) === null) {
  console.log("Value not present\n");
} else {
  console.log("Present");
}

Java

public class BinarySearchLinkedList {
    public static class Node {
        int val;
        Node next;

        public Node(int val) {
            this.val = val;
            this.next = null;
        }
    }

    static Node push(Node head, int val) {
        Node newNode = new Node(val);
        newNode.next = head;
        head = newNode;
        return head;
    }

    static Node middleNode(Node start, Node last) {
        if (start == null) {
            return null;
        }

        Node slow = start;
        Node fast = start.next;

        while (fast != last) {
            fast = fast.next;

            if (fast != last) {
                slow = slow.next;
                fast = fast.next;
            }
        }

        return slow;
    }

    static Node binarySearchLinkedList(Node head, int targetVal) {
        Node start = head;
        Node last = null;

        do {
            Node mid = middleNode(start, last);

            if (mid == null) {
                return null;
            }

            if (mid.val == targetVal) {
                return mid;
            } else if (mid.val > targetVal) {
                start = mid.next;
            } else {
                last = mid;
            }
        } while (last == null || last != start);

        return null;
    }

    public static void main(String[] args) {
        Node head = null;

        head = push(head, 1);
        head = push(head, 4);
        head = push(head, 7);
        head = push(head, 8);
        head = push(head, 9);
        head = push(head, 10);

        int x = 7;

        if (binarySearchLinkedList(head, x) == null) {
            System.out.println("Value not present");
        } else {
            System.out.println("Present");
        }
    }
}

C

#include <stdio.h>
#include <stdlib.h>

struct Node
{
    int val;
    struct Node *next;
};

void push(struct Node **head_ref, int new_val)
{
    struct Node *new_node = (struct Node *)malloc(sizeof(struct Node));

    new_node->val = new_val;

    new_node->next = (*head_ref);

    (*head_ref) = new_node;
}

struct Node *middleNode(struct Node *start, struct Node *last)
{
    if (start == NULL)
    {
        return NULL;
    }

    struct Node *slow = start;
    struct Node *fast = start->next;

    while (fast != last)
    {
        fast = fast->next;

        if (fast != last)
        {
            slow = slow->next;
            fast = fast->next;
        }
    }

    return slow;
}

struct Node *binarySearchLinkedList(struct Node *head, int target_val)
{
    struct Node *start = head;
    struct Node *last = NULL;

    do
    {
        struct Node *mid = middleNode(start, last);

        if (mid == NULL)
        {
            return NULL;
        }

        if (mid->val == target_val)
        {
            return mid;
        }
        else if (mid->val < target_val)
        {
            start = mid->next;
        }
        else
        {
            last = mid;
        }
    } while (last == NULL || last != start);

    return NULL;
}

int main()
{
    struct Node *head = NULL;

    push(&head, 2);
    push(&head, 3);
    push(&head, 5);
    push(&head, 10);
    push(&head, 15);
    push(&head, 20);

    int x = 10;

    if (binarySearchLinkedList(head, x) == NULL)
    {
        printf("Value not present\n");
    }
    else
    {
        printf("Present\n");
    }

    return 0;
}

刷題：33. Search in Rotated Sorted Array

題目

連結

You are given an integer array nums sorted in ascending order, and an integer target.

Suppose that nums is rotated at some pivot unknown to you beforehand (i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]).

If target is found in the array return its index, otherwise, return -1.

Related Topics
Array, Binary Search

Example 1:

Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4

Constraints:

* 1 <= nums.length <= 5000
* -10^4 <= nums[i] <= 10^4
* All values of nums are unique.
* nums is guaranteed to be rotated at some pivot.
* -10^4 <= target <= 10^4

思考

這題好玩的地方在於本來是排列整齊的數列，然後從某一個點斷裂成兩截，前後互換形成 Rotated Sorted Array。

[0,1,2,4,5,6,7] -> [4,5,6,7,0,1,2]

這題仍然可以用 Binary Search 來搜尋，只是大小邊界的判斷要多花點功夫才行：

• 判斷最小值是大於還是小於等於中間值
  • 最小值 小於等於 中間值
    • 表示中間值的左半邊都是正常排序
    • 判斷目標值有沒有在左半邊
      • 有，修改最大值為中間值減一
      • 沒有，表示在右半邊，修改最小值為中間值加一
  • 最小值 大於 中間值
    • 表示中間值的右半邊是正常排序
    • 判斷目標值有沒有在右半邊
      • 有，修改最小值為中間值加一
      • 沒有，表示在左半邊，修改最大值為中間值減一

解題

JS

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
const search = function (nums, target) {
  let low = 0;
  let high = nums.length - 1;

  while (low <= high) {
    let mid = (low + high) >> 1;

    if (target == nums[mid]) {
      return mid;
    } else if (nums[low] <= nums[mid]) {
      if (nums[low] <= target && target < nums[mid]) {
        high = mid - 1;
      } else {
        low = mid + 1;
      }
    } else {
      if (nums[mid] < target && target <= nums[high]) {
        low = mid + 1;
      } else {
        high = mid - 1;
      }
    }
  }

  return -1;
};

Java

class Solution {
    public int search(int[] nums, int target) {
        int low = 0;
        int high = nums.length - 1;

        while (low <= high) {
            int mid = (low + high) >> 1;

            if (target == nums[mid]) {
                return mid;
            } else if (nums[low] <= nums[mid]) {
                if (nums[low] <= target && target < nums[mid]) {
                    high = mid - 1;
                } else {
                    low = mid + 1;
                }
            } else {
                if (nums[mid] < target && target <= nums[high]) {
                    low = mid + 1;
                } else {
                    high = mid - 1;
                }
            }
        }

        return -1;
    }
}

C

int search(int *nums, int numsSize, int target)
{
    int low = 0;
    int high = numsSize - 1;

    while (low <= high)
    {
        int mid = (low + high) >> 1;

        if (target == nums[mid])
        {
            return mid;
        }
        else if (nums[low] <= nums[mid])
        {
            if (nums[low] <= target && target < nums[mid])
            {
                high = mid - 1;
            }
            else
            {
                low = mid + 1;
            }
        }
        else
        {
            if (nums[mid] < target && target <= nums[high])
            {
                low = mid + 1;
            }
            else
            {
                high = mid - 1;
            }
        }
    }

    return -1;
}

結論

如果能使用 Binary Search 就盡量使用，當在資料越來越多樣性，毫無章法的環境來看，實在是過於理想的念頭。因此，平常讓資料庫有定期整理、排序的排程，讓資料盡可能是排序完成的狀態，如此一來，就可以減少搜尋時的時間消耗。